The present invention relates to a high-speed lookup apparatus as well as a high-speed lookup method for retrieving data at high-speed from a table in which it is stored, matching data provided.
In recent years there has been a rapid increase in the application of networks which use Internet Protocols (IP) as their network layer protocols, to the Internet and to enterprise networks. In accordance with this increase, there is a demand for more high performance in the IP routers which carry out the relaying processing on packets in the IP network. However, the relaying processing of IP packets is performed based on routing information, which manages relaying route selection for the packets in network address (network prefix) units. This network address uses one part of the IP address. That xe2x80x9cone partxe2x80x9d is an address value defined, for example, with a variable length from the upper part of an address, and the length (prefix length) takes different values depending upon the network address (network prefix). Namely, the field, which is used to represent a network and is a part of an address showing destination for each packet varies according to network addresses. Therefore, if a certain packet is to be relayed, in order to obtain the information corresponding to the network address (network prefix) from the destination address of the packet, it is necessary to perform a comparison process using data lengths that differ for each route entry when referencing the management table. Consequently, to make relay processing of IP packets high-speed, it is necessary to perform a high-speed lookup of the routing information holding this variable length prefix.
Thus, since the comparison object field takes on a different value with each entry, several approaches to high-speed lookup have been undertaken in the past. For example, high-speed radix tree and radish tree algorithms are employed for the network processing in Berkley Software Distribution (BSD) OSs, the Transmission Control Protocol/Internet Protocol (TCP/IP) implementation reference. With these types of algorithms, an entry is created that shows the existence of a branch object bit, in the location in the address field where an entry candidate first branches, in order from the most significant bit on downward. Then, based on the xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d value of the branch object bit (check object bit), the possible entry is classified according to the bit sequence that follows. Therefore, a lookup proceeds to a bit location where a branch candidate is to be branched, and branches depending upon the value found there, tracing through the tree in order until a point is found that has no branch, and then determines whether the arrived at entry satisfies the lookup conditions. However, with this type of tree based algorithm, the number of branches needed to arrive at a single entry is not the same for each entry. Depending upon the conditions, it may take only one branch to arrive at a certain entry, while for a different entry, in a worst case scenario it is possible that it may take as many repeating branches as the address length. Further, even if an attempt is made to perform the algorithm in hardware in order to make it high-speed, each step in the lookup process is dependent, so it is difficult to speed it up by means of pipeline processing or bubble processing. A Content Addressable Memory (CAM) is in use as a technique of performing high-speed hardware lookups. However, as explained above, routing information lookups have different lengths for each entry, so the CAM, with fixed length data lookup, cannot be used as is, but must be coupled with a route cache or other technique. A route cashe maintains as a list correspondence between an object address and its matching entry after a lookup is first performed, and it is easy to use the CAM and construct a lookup apparatus. However, the entries which is represented by a network address, namely a kind of address aggregate, are handled as their developed forms of separate address units, and to hold an equivalent amount of information, a much larger table size is needed. On the other hand, if the table size is restrained, the number of cases in which there is no hit in the cache will increase, so there is a problem in that to get high-speed with a route cache does not work well.
In addition, there are techniques of constructing a tree with multiple bit units, but the tree branch locations become fixed bit locations. For that reason, in an application in which every comparison object takes a different value for bit width, it is necessary to construct a table in which the address is developed in some form as in the case of the route cache. This means that one cannot escape a greatly enlarged table size. To avoid this problem, a structure that accommodates a portion in a cache like manner must be used, but this has poor efficiency, just like the route cache described above.
A xe2x80x9cMasked Lookup Memory Circuitxe2x80x9d (Japanese Patent Application Laid-open Nos. Hei 3-12896, Hei 7-143156, Hei 10-112728, etc.) exists that uses a structure in which a mask bit is added to the prior type CAM memory in order to set the comparison object bit separately for each entry. In this circuit, the data length, which is set independently for every entry indispensable for routing information lookup on the IP network, is included at the CAM level, but with the degree of semiconductor integration, etc., it is not always possible to ensure a capacity that will store all of the routing information.
Therefore, an object of the present invention is that by combining means for a masked lookup memory with a tree or a multistage indexed type memory table, to be able to perform lookup, not only will the problems of unbalanced lookup time and an increased table volume be eased, but even if only a small amount of masked lookup memory can be used, a lookup process possessing a large lookup table will be realized.
In order to solve the above object, a high-speed lookup method of the present invention comprises the steps of: dividing entries, which become lookup objects and have variable length comparison conditions, into a plurality of groups, taking a representative lookup key as lookup data for each of the groups, and storing mask data that sets a range for matching with a match candidate, as well as comparison object data in a masked lookup memory means so that setting can be made for each of said entries; and obtaining, from the masked lookup memory means, information corresponding to the groups that match the lookup conditions, and limiting the lookup object entries to the data within the object group.
This structure further comprises the steps of: classifying the entries, which become lookup objects, into a tree state, with nodes adopted at points where bit values are either xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d, in order from the first bit; and performing a lookup for matching entries after the entries, which have been classified into the tree state, are limited to the data within the object groups.
In addition, it may further comprises the steps of: constructing a tree for all of the entries as lookup objects; selecting an intermediate node location as a virtual entry representative of the lookup group by coming upstream by a fixed number of hops from the farthest point from the tip root, out of all the leaves at the distal ends of the tree; excluding branches below the node location of the selected virtual entry and repeating the procedure; storing the selected virtual entries in the masked lookup memory means until all of the entries have been covered; determining during lookup whether the virtual entry matches the conditions by referencing the masked lookup memory means; and performing further lookups using the tree.
The above high-speed lookup method further comprises the step of, when lookup occurs within the object group, performing a lookup in a table using a table lookup offset determined by the region from where the lookup key value bit string from the lookup object entry within the group first differs, up to the longest data length. This structure, when determining the representative virtual entry from the lookup group, may further comprises the steps of: classifying the lookup object entry into a tree state with nodes adopted at points where bit values are either xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d, in order from the first bit; taking branches, in which the branch bit locations are unevenly distributed, as the group and performing a lookup by the masked lookup memory means until a group that matches the conditions is found; and performing further lookups with reference to the table.
The high-speed lookup apparatus of the present invention comprises: a masked lookup memory means that divides entries, which become lookup objects and have variable length comparison conditions, into a plurality of groups, takes a representative lookup key as lookup data for each group, and stores the mask data, which sets a range for matching with a match candidate, as well as the comparison object data so that setting can be made for each of the entries; and a lookup means that obtains, from the masked lookup memory means, information corresponding to the groups that match the lookup conditions, and limits the lookup object entries to the data within the object group.
This structure further comprises a tree construction means which classifies the entries, which become lookup objects, into a tree state, with nodes adopted at points where bit values are either xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d, in order from the first bit, in which the lookup means performs lookup for matching entries after the entries, which have been classified into the tree state, are limited to the data within the object groups.
In addition, the tree construction means constructs a tree for all of the lookup object entries, selects an intermediate node location as a virtual entry representative of the lookup group by coming upstream by a fixed number of hops from the farthest point from the tip root, out of all the leaves at the distal end of the tree, excludes branches below the node location of the selected virtual entry and repeats the procedure, and stores the selected virtual entry in the masked lookup memory means until all of the entries have been covered, and the lookup means determines during lookup whether the virtual entry matches the conditions by referencing the masked lookup memory means, and a further lookup is performed using the tree.
The above high-speed lookup apparatus further comprises a memory means that, when the lookup means is performing lookup within the object group, creates a lookup table within the group as a table lookup offset, from the first location where a bit string differs to the longest data length, through the lookup key value of the lookup object entry.
This structure further comprises a tree construction means that classifies the lookup object entry into a tree state with nodes adopted at points where bit values are either xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d, in order from the first bit, in which, during determination of a representative virtual entry of a lookup group, the lookup means takes branches where the branch bit locations are unevenly distributed as a group, and performs a lookup by the masked lookup memory means until a group that matches the conditions is found, and performs further lookups with reference to the table.
Both the high-speed lookup method and the high-speed lookup apparatus can be applied to a router that performs forwarding of packets based on entries corresponding to routing information, in a network that provide communication conforming to an IP protocol.
In the present invention, when constructing the lookup tree, the branchpoints are registered in the masked memory means as virtual entries when the number of branches to the tip is less than a fixed value, or the common portion of the bit strings from multiple routing information entries are stored in the masked lookup memory as virtual entries. And by maintaining information on the each of the remaining entries, where the differing address fields are stored in a conventional table form as indexes, the number of lookup levels and the table size can be reduced when compared to a conventional multistage table arrangement.
By performing a primary classification of the routing lookup by the masked lookup memory in this way, the remaining lookup processing volume can be reduced.